package com.copa.l692;

import java.util.*;

/**
 * @author copa
 * @createDate 2022-06-14 11:53
 * @function 哈希表+堆
 */
public class Test1 {

    public List<String> topKFrequent(String[] words, int k) {
        HashMap<String, Integer> hashMap = new HashMap<>();
        for (String word : words) {
            if (hashMap.containsKey(word)) {
                hashMap.put(word, hashMap.get(word) + 1);
                continue;
            }
            hashMap.put(word, 1);
        }

        PriorityQueue<String> queue = new PriorityQueue<>(
                (w1, w2) -> hashMap.get(w1).equals(hashMap.get(w2)) ? w2.compareTo(w1) : hashMap.get(w1) - hashMap.get(w2)
        );

        for (Map.Entry<String, Integer> entry : hashMap.entrySet()) {
            queue.add(entry.getKey());
            if (queue.size() > k) {
                queue.poll();
            }
        }

        List<String> result = new ArrayList<>();
        while (!queue.isEmpty()) {
            result.add(queue.poll());
        }

        Collections.reverse(result);
        return result;
    }

    public static void main(String[] args) {
        String[] words = {"i", "love", "leetcode", "i", "love", "coding"};
        List<String> result = new Test1().topKFrequent(words, 2);
        for (String s : result) {
            System.out.println(s);
        }
    }
}
